1. Field of Invention
The present invention relates generally to methods and apparatus for transmitting digital data in cable television network systems. More specifically, the present invention relates to methods and apparatus for dynamically adjusting modem back-off parameters in a cable modem network.
2. Background
The cable TV industry has been upgrading its signal distribution and transmission infrastructure since the late 1980s. In many cable television markets, the infrastructure and topology of cable systems now include fiber optics as part of its signal transmission component. This has accelerated the pace at which the cable industry has taken advantage of the inherent two-way communication capability of cable systems. The cable industry is now poised to develop reliable and efficient two-way transmission of digital data over its cable lines at speeds orders of magnitude faster than those available through telephone lines, thereby allowing its subscribers to access digital data for uses ranging from Internet access to cablecommuting.
Originally, cable TV lines were exclusively coaxial cable. The system included a cable head end, i.e. a distribution hub, which received analog signals for broadcast from various sources such as satellites, broadcast transmissions, or local TV studios. Coaxial cable from the head end was connected to multiple distribution nodes, each of which could supply many houses or subscribers. From the distribution nodes, trunk lines (linear sections of coaxial cable) extended toward remote sites on the cable network. A typical trunk line is about 10 kilometers. Branching off of these trunk lines were distribution or feeder cables (40% of the system""s cable footage) to specific neighborhoods, and drop cables (45% of the system""s cable footage) to homes receiving cable television. Amplifiers were provided to maintain signal strength at various locations along the trunk line. For example, broadband amplifiers are required about every 2000 feet depending on the bandwidth of the system. The maximum number of amplifiers that can be placed in a run or cascade is limited by the build-up of noise and distortion. This configuration, known as tree and branch, is still present in older segments of the cable TV market.
With cable television, a TV analog signal received at the head end of a particular cable system is broadcast to all subscribers on that cable system. The subscriber simply needed a television with an appropriate cable receptor to receive the cable television signal. The cable TV signal was broadcast at a radio frequency range of about 60 to 700 MHz. Broadcast signals were sent downstream; that is, from the head end of the cable system across the distribution nodes, over the trunk line, to feeder lines that led to the subscribers. However, the cable system did not have installed the equipment necessary for sending signals from subscribers to the head end, known as return or upstream signal transmission. Not surprisingly, nor were there provisions for digital signal transmission either downstream or upstream.
In the 1980s, cable companies began installing optical fibers between the head end of the cable system and distribution nodes (discussed in greater detail with respect to FIG. 1). The optical fibers reduced noise, improved speed and bandwidth, and reduced the need for amplification of signals along the cable lines. In many locations, cable companies installed optical fibers for both downstream and upstream signals. The resulting systems are known as hybrid fiber-coaxial (HFC) systems. Upstream signal transmission was made possible through the use of duplex or two-way filters. These filters allow signals of certain frequencies to go in one direction and of other frequencies to go in the opposite direction. This new upstream data transmission capability allowed cable companies to use set-top cable boxes and allowed subscribers pay-per-view functionality, i.e. a service allowing subscribers to send a signal to the cable system indicating that they want to see a certain program.
In addition, cable companies began installing fiber optic lines into the trunk lines of the cable system in the late 1980s. A typical fiber optic trunk line can be upto 80 kilometers, whereas a typical coaxial trunk line is about 10 kilometers, as mentioned above. Prior to the 1990s, cable television systems were not intended to be general-purpose communications mechanisms. Their primary purpose was transmitting a variety of entertainment television signals to subscribers. Thus, they needed to be one-way transmission paths from a central location, known as the head end, to each subscriber""s home, delivering essentially the same signals to each subscriber. HFC systems run fiber deep into the cable TV network offering subscribers more neighborhood specific programming by segmenting an existing system into individual serving areas between 500 to 2,000 subscribers. Although networks using exclusively fiber optics would be optimal, presently cable networks equipped with HFC configurations are capable of delivering a variety of high bandwidth, interactive services to homes for significantly lower costs than networks using only fiber optic cables.
FIG. 1 is a block diagram of a two-way hybrid fiber-coaxial (HFC) cable system utilizing a cable modem for data transmission. It shows a head end 102 (essentially a distribution hub) which can typically service about 40,000 subscribers. Head end 102 contains a cable modem termination system (CMTS) 104 that is needed when transmitting and receiving data using cable modems. Block 104 of FIG. 1 represents a cable modem termination system connected to a fiber node 108 by pairs of optical fibers 106. The primary functions of the CMTS are (1) receiving signals from external sources 100 and converting the format of those signals, e.g., microwave signals to electrical signals suitable for transmission over the cable system; (2) providing appropriate MAC level packet headers (as specified by the MCNS standard discussed below) for data received by the cable system, (3) modulating and demodulating the data to and from the cable system, and (4) converting the electrical signal in the CMTS to an optical signal for transmission over the optical lines to the fiber nodes.
Head end 102 is connected through pairs of fiber optic lines 106 (one line for each direction) to a series of fiber nodes 108. Each head end can support normally up to 80 fiber nodes. Pre-HFC cable systems used coaxial cables and conventional distribution nodes. Since a single coaxial cable was capable of transmitting data in both directions, one coaxial cable ran between the head end and each distribution node. In addition, because cable modems were not used, the head end of pre-HFC cable systems did not contain a CMTS. Returning to FIG. 1, each of the fiber nodes 108 is connected by a coaxial cable 110 to two-way amplifiers or duplex filters 112 which permit certain frequencies to go in one direction and other frequencies to go in the opposite direction (frequency ranges for upstream and downstream paths are discussed below). Each fiber node 108 can normally service upto 500 subscribers. Fiber node 108, coaxial cable 110, two-way amplifiers 112, plus distribution amplifiers 114 along trunk line 116, and subscriber taps, i.e. branch lines 118, make up the coaxial distribution system of an HFC system. Subscriber tap 118 is connected to a cable modem 120. Cable modem 120 is, in turn, connected to a subscriber computer 122.
Recently, it has been contemplated that HFC cable systems could be used for two-way transmission of digital data. The data may be Internet data, digital audio, or digital video data, in MPEG format, for example, from one or more external sources 100. Using two-way HFC cable systems for transmitting digital data is attractive for a number of reasons. Most notably, they provide upto a thousand times faster transmission of digital data than is presently possible over telephone lines. However, in order for a two-way cable system to provide digital communications, subscribers must be equipped with cable modems, such as cable modem 120. With respect to Internet data, the public telephone network has been used, for the most part, to access the Internet from remote locations. Through telephone lines, data is typically transmitted at speeds ranging from 2,400 to 33,600 bits per second (bps) using commercial (and widely used) data modems for personal computers. Using a two-way HFC system as shown in FIG. 1 with cable modems, data may be transferred at speeds up to 10 million bps. Table 1 is a comparison of transmission times for transmitting a 500 kilobyte image over the Internet.
Furthermore, subscribers can be fully connected twenty-four hours a day to services without interfering with cable television service or phone service. The cable modem, an improvement of a conventional PC data modem, provides this high speed connectivity and is, therefore, instrumental in transforming the cable system into a full service provider of video, voice and data telecommunications services.
As mentioned above, the cable industry has been upgrading its coaxial cable systems to HFC systems that utilize fiber optics to connect head ends to fiber nodes and, in some instances, to also use them in the trunk lines of the coaxial distribution system. In way of background, optical fiber is constructed from thin strands of glass that carry signals longer distances and faster than either coaxial cable or the twisted pair copper wire used by telephone companies. Fiber optic lines allow signals to be carried much greater distances without the use of amplifiers (item 114 of FIG. 1). Amplifiers decrease a cable system""s channel capacity, degrade the signal quality, and are susceptible to high maintenance costs. Thus, distribution systems that use fiber optics need fewer amplifiers to maintain better signal quality.
In cable systems, digital data is carried over radio frequency (RF) carrier signals. Cable modems are devices that convert digital data to a modulated RF signal and convert the RF signal back to digital form. The conversion is done at two points: at the subscriber""s home by a cable modem and by a CMTS located at the head end. The CMTS converts the digital data to a modulated RF signal which is carried over the fiber and coaxial lines to the subscriber premises. The cable modem then demodulates the RF signal and feeds the digital data to a computer. On the return path, the operations are reversed. The digital data is fed to the cable modem which converts it to a modulated RF signal (it is helpful to keep in mind that the word xe2x80x9cmodemxe2x80x9d is derived from modulator/demodulator). Once the CMTS receives the RF signal, it demodulates it and transmits the digital data to an external source.
As mentioned above, cable modem technology is in a unique position to meet the demands of users seeking fast access to information services, the Internet and business applications, and can be used by those interested in cablecommuting (a group of workers working from home or remote sites whose numbers will grow as the cable modem infrastructure becomes increasingly prevalent). Not surprisingly, with the growing interest in receiving data over cable network systems, there has been an increased focus on performance, reliability, and improved maintenance of such systems. In sum, cable companies are in the midst of a transition from their traditional core business of entertainment video programming to a position as a full service provider of video, voice and data telecommunication services. Among the elements that have made this transition possible are technologies such as the cable modem.
Although not fully agreed to by all parties in the cable TV and cable modem industry, an emerging standard establishing the protocol for two-way communication of digital data on cable systems has been defined by a consortium of industry groups. The protocol, known as the Multimedia Cable Network System (MCNS), specifies particular standards regarding the transmission of data over cable systems.
FIG. 2 is a block diagram of a two-way hybrid fiber-coaxial (HFC) cable system including cable modems and a network management station. The main distribution component of an HFC cable system is a primary (or secondary) hub 202 which can typically service about 40,000 subscribers or end-users. Hub 202 contains several components of which two, relevant to this discussion, are shown in FIG. 2. One component is a cable modem termination system or, CMTS, 204 needed when transmitting data (sending it downstream to users) and receiving data (receiving upstream data originating from users) using cable modems, shown as boxes 206, 208, 210, and 212. Another component is a fiber transceiver 214 used to convert electrical signals to optical signals for transmission over a fiber optic cable 216. Fiber optic cable 216 can typically run for as long as 200 km and is used to carry data (in one direction) for most of the distance between hub 202 to a neighborhood cable TV plant 217. More specifically, fiber optic cable 216 is a pair of cablesxe2x80x94each one carrying data in one direction. When the data reaches a particular neighborhood cable TV plant 217, a fiber node 218 converts the data so that it can be transmitted as electrical signals over a conventional coaxial cable 220, also referred to as a trunk line. Hub 202 can typically support up to 80 fiber nodes and each fiber node can support up to 500 or more subscribers. Thus, there are normally multiple fiber optic cables emanating from hub 202 to an equal number of fiber nodes. In addition, the number of subscribers as well as fiber capacity is currently increasing due to dense wave-division multiplexing technology. DWDM is a technique for transmitting on more than one wavelength of light on the same fiber.
Cable TV (CTV) taps 222 and 224 are used to distribute a data signal to individual cable modems 206 and 210 (from CTV tap 224) and modems 208 and 212 (from CTV tap 222). Two-way cable TV amplifiers 226 and 228 are used to amplify signals as they are carried over coaxial cable 220. Data can be received by the cable modems shown (each CTV tap can have output cables servicing multiple cable modems) and transmitted back to hub 202. In cable systems, digital data is carried over radio frequency (RF) carrier signals. Cable modems are devices that modulate an RF signal to a digital signal and demodulate a digital signal to an RF signal for transmission over a coaxial cable. This modulation/demodulation is done at two points: by a cable modem at the subscriber""s home and by CMTS 204 located at hub 202. If CMTS 204 receives digital data, for example from the Internet, it converts the digital data to a modulated RF signal which is carried over the fiber and coaxial lines to the subscriber premises. A cable modem then demodulates the RF signal and feeds the digital data to a computer (not shown). On the return path, the operations are reversed. The digital data is fed to the cable modem which converts it to a modulated RF signal. Once CMTS 204 receives the RF signal, it demodulates it and transmits the digital data to an external source.
Data packets are addressed to specific modems or to a hub (if sent upstream) by a MAC layer 230 in CMTS 204 at hub 202 (there is also a MAC addressing component, not shown, in the cable modems that encapsulate data with a header containing the address of the hub when data is being sent upstream). CMTS 204 has a physical layer 232 for receiving and transmitting RF signals on the HFC cable plant. The main purpose of MAC layer 230 is to encapsulate a data packet within a MAC header according to the DOCSIS standard for transmission of data. This standard is currently a draft recommendation (J.isc Annex B) which has been publicly presented to Study Group 9 of the ITU in October 1997, and is known to persons in the cable modem data communication field. MAC layer 230 contains the necessary logic to encapsulate data with the appropriate MAC addresses of the cable modems on the system. Each cable modem on the system has its own MAC address. Whenever a new cable modem is installed, its address is registered with MAC layer 230. The MAC address is necessary to distinguish data going from the cable modems since all modems share a common upstream path, and so that CMTS 204 knows where to send data. Thus, data packets, regardless of format, are mapped to a particular MAC address. MAC layer 230 is also responsible for sending out polling messages as part of the link protocol between the CMTS and the cable modems that is necessary to maintain a communication connection between the two.
Basic data connectivity on the cable system typically requires a single upstream channel (to carry return signals from the cable modem to the cable head-end) and a single downstream channel carrying signals from the head-end to the cable modems. A cable access network typically comprises multiple upstream channels and multiple downstream channels.
On the downstream cable data channel, data is broadcast by a single head-end (CMTS) to cable modems served on that downstream channel. However, the upstream channel is complicated by the fact that it is used as a multiple access channel which is shared by the large group of cable modems (on that channel) to communicate with the CMTS. The upstream channel is time-slotted and cable modems need to contend for gaining access to the CMTS in this shared channel.
As mentioned previously, each DOCSIS upstream cable channel is time-slotted. The basic unit of scheduling is a minislot. The CMTS remotely schedules each and every minislot on the upstream channel. Some contiguous minislots are grouped together as a unicast data slot meant to be used by a specific cable modem for sending its data upstream. Some minislots are marked as contention slots that can be used by any cable modem to send ranging/bandwidth requests upstream to the CMTS. The CMTS conveys this minislot allocation information (to the set of modems sharing the upstream channel) ahead of time using bandwidth allocation MAP messages which are periodically broadcast on the downstream channel. In general any given upstream channel [i] includes two logical sub-channels: a contention sub-channel comprising contention minislots which can be used by any cable modem, and a reservation or grant sub-channel comprising minislots allocated to specific cable modems. This is shown, for example, in FIG. 3 of the drawings.
FIG. 3A illustrates the various types of minislots allocated by the CMTS on the upstream channel[i] 300. FIGS. 3B and 3C illustrate the initial ranging subchannel and bandwidth-request subchannel which are included in the upstream channel 300 of FIG. 3A.
For simplification purposes, and to avoid confusion, the xe2x80x9c[i]xe2x80x9d portion of the upstream or downstream channel and/or elements related thereto may not be included in the discussion below. However, it is to be understood that the techniques described herein with respect to a particular channel may also be applied to other channels in the network.
There are two basic types of contention slots allocated by the CMTS on the upstream, each being used for a different purpose by the cable modems. A first type of contention slot is an Initial Ranging Slot, identified in FIG. 3A as slot 301. This contention slot on the upstream is made up of a group of minislots forming a 2 ms wide time slice. This region is intended to be used only by xe2x80x9cnewxe2x80x9d cable modems during their cable interface initialization phase to join the HFC network, such as, for example, during initial powering up of the cable modem. Once the CMTS receives an initial ranging request from a new modem in this type of slot, the CMTS subsequently polls the modem (along with other modems identified in the network) using unicast (non-contention) station maintenance slots (not shown in FIG. 3).
A second type of contention slot is a Bandwidth-Request Minislot. The CMTS marks some of the upstream minislots as contention based bandwidth-request minislots, as shown, for example, by slot 305 of FIG. 3A. Any cable modem having upstream data to send, can/will use this type of minislot to request the CMTS for a data grant (slot 303, FIG. 3A) in which to send its actual data in non-contention mode. The stream of initial ranging slots and the bandwidth-request slots form two independent contention subchannels on each upstream channel as shown in FIGS. 3B and 3C, namely the initial ranging subchannel and bandwidth-request subchannel, respectively. For purposes of simplification, initial ranging slots and bandwidth-request slots will collectively be referred to as xe2x80x9ccontention slotsxe2x80x9d or xe2x80x9ccontention minislots.xe2x80x9d
As per the DOCSIS Cable MAC protocol, a common method of contention resolution on the upstream multiple access channel is through the use of a truncated binary exponential back-off algorithm in which the back-off window is controlled by the CMTS. The initial and final back-off windows are specified by the CMTS in the form of back-off start (BS) and back-off end (BE) parameters in the channel MAPs. These back-off window parameters are expressed as a power of two. For example, a back-off window parameter of 5 indicates a window of 25=32 random numbers, selected from the range 0-31. When a cable modem collides for the first time, it sets its internal back-off window equal to the back-off start window parameter specified by the CMTS in the upstream channel MAP. It then picks a random number from this window of numbers. The random number chosen by the modem (herein referred to as a modem back-off value) is the number of contention slots it will defer before re-transmitting its request to the CMTS. Since each of the colliding modems independently picks a random number from this window, the chances of more than one modem choosing the same random number is low.
Thus the modems usually succeed in their second attempt. However if the number of modems that had originally collided is large, as compared to the window of slots that each modem is using for choosing its random number, there is a high probability that at least two modems will select the same random number and collide again. Each time the modems collide, they increment their internal back-off window by one, until the back-off window reaches the value of the back-off end parameter. Thus back-off end represents the largest window of numbers from which to select the number of deferred contention slots.
From the above explanation, it can be seen that the proper choice of an internal back-off window at the cable modem is an important factor for access-delay/throughput performance in the contention channel. When the original number of colliding modems is relatively small, it is preferable that the modem selects a random number from a small back-off window. The small back-off window ensures that the modem is not unnecessarily backing-off too many contention slots, thereby incurring unnecessary access delay. On the other hand, in the case of a regional power outage, for example, many cable modems will be contending at the same time to communicate with the CMTS. In this situation, a small back-off window will result in very poor performance since the modems will not be sufficiently randomized over time to prevent collisions due to more than one modem contending for the same contention slot. Thus, where the number of modems that had originally collided is large, it is preferable that a large internal back-off window be used so that the colliding modems are well randomized in time for their retransmissions.
There is no single, fixed back-off window value that works well for all upstream contention load scenarios. It is desirable, therefore, for the CMTS to incorporate an intelligent technique to estimate how many modems are currently involved in the collision resolution process, and to dynamically adjust the back-off window parameters (in the channel MAPs) accordingly. Additionally, it is desirable to provide a technique for dynamically estimating the number of cable modems simultaneously contending for upstream access in order to provide for improved access delay and improved throughput performance in the upstream contention sub-channels of the cable modem network. Further, it is desirable to provide a cost-effective technique for determining cable modem back-off parameters which may be easily implemented and rapidly executed in existing cable modem network systems.
According to specific embodiments of the invention, a technique is provided for dynamically adjusting modem back-off parameters in a cable modem network. The technique of the present invention provides for improved access delay and improved throughput performance in contention sub-channels of cable access networks, particularly those involving large round trip delays. Additionally, the technique of the present invention utilizes elementary CPU operations, making it a viable and cost-efficient solution which is easily implemented and allows for rapid execution in existing cable modem network systems. Furthermore, the technique of the present invention is able to track the number of contending cable modems in a network over a much larger range than previous techniques.
According to a specific embodiment of the present invention, a method is provided for dynamically adjusting modem back-off parameters in a cable modem network. The cable modem network includes a Cable Modem Termination System (CMTS), and includes a plurality of cable modems. The modem back-off parameters are utilized by the cable modems to determine a deferment period during which communication requests to the CMTS on the upstream channel are not attempted. The back-off parameters include a back-off start (BS) parameter and a back-off end (BE) parameter. The method comprises the steps of determining a number (Ns) of contention slots in a sampling interval in which modem requests are successfully received by the CMTS; determining a number (Nc) of contention slots in the sampling interval in which modem requests are unsuccessfully received by the CMTS due to collisions with at least one other modem request; dynamically adjusting the modem back-off parameters based upon a ratio of the Ns and Nc parameters; and communicating the dynamically adjusted back-off parameters to the plurality of cable modems in the network. An additional aspect of this embodiment includes the steps of increasing the back-off start parameter if the ratio of Nc/Ns is greater than a first specified value; and decreasing the back-off start parameter if the ratio of Nc/Ns is less than a second specified value.
A second specific embodiment of the present invention provides a method for dynamically adjusting modem back-off parameters in a cable modem network. The method comprises the steps of comparing estimates of a first number (Ns) of modem request successfully received by the CMTS with a second number (Nc) of modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for the same contention slot; dynamically adjusting themodem back-off parameters based upon the comparison of the Ns and Nc values, wherein the dynamic adjustment of the back-off parameters is not based upon a value representing a number of empty or unused contention slots; and communicating the dynamically adjusted back-off parameters to the plurality of cable modems in the network. An additional aspect of this embodiment includes the steps of increasing the back-off start parameter if the ratio of Nc/Ns is greater than a first specified value; and decreasing the back-off start parameter if the ratio of Nc/Ns is less than a second specified value.
A third specific embodiment provides an apparatus for dynamically adjusting modem back-off parameters in a cable modem network. The apparatus comprises, among other things, a counter for determining a number (Ns) of contention slots in a sampling interval in which modem requests are successfully received by the CMTS; a counter for determining a number (Nc) of contention slots in the sampling interval in which modem requests are unsuccessfully received by the CMTS due to collisions with at least one other modem request; means for dynamically adjusting the modem back-off parameters based upon a ratio of the Ns and Nc parameters; and means for communicating the dynamically adjusted back-off parameters to the plurality of cable modems. The back-off parameters include a back-off start (BS) parameter and a back-off end (BE) parameter. The means for dynamically adjusting the modem back-off parameters may also include means for increasing the back-off start parameter if the ratio of Nc/Ns is greater than the first specified value; and means for decreasing the back-off start parameter if the ratio of Nc/Ns is less than a second specified value.
A fourth specific embodiment of the present invention provides a cable modem termination system in a cable modem network comprising, among other things, means for comparing estimates, within a specified time interval, of a first number (Ns) of upstream modem requests successfully received by the CMTS and a second number (Nc) of upstream modem requests unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot; and means for dynamically adjusting the modem back-off parameters based upon the Ns parameter and the Nc parameter, wherein the dynamic adjustment of the back-off parameters is not based upon a value representing a number of empty or unused contention slots. Additionally, the system comprises means for communicating the dynamically adjusted back-off parameters to the plurality of cable modems, wherein the cable modem back-off parameters are utilized by the cable modems to determine a deferment period during which communication requests to the CMTS are not attempted. The back-off parameters include a back-off start (BS) parameter and a back-off end (BE) parameter. The means for dynamically adjusting the modem back-off parameters may also include means for increasing the back-off start parameter if the ratio of Nc/Ns is greater than the first specified value; and means for decreasing the back-off start parameter if the ratio of Nc/Ns is less than a second specified value.
A fifth specific embodiment of the present invention provides a computer program product for dynamically adjusting modem back-off parameters in a cable modem network. The cable modem network includes a CMTS and a plurality of cable modems. The modem back-off parameters are utilized by the cable modems to determine a deferment period during which upstream communication requests to the CMTS are not attempted. The back-off parameters include a back-off start parameter and a back-off end parameter. The computer program product comprises a computer usable medium having computer readable code embodied therein. The computer readable code comprises computer code for comparing estimates, within a specified time interval, of a first number (Ns) of modem requests successfully received by the CMTS and a second number (Nc) of modem request unsuccessfully received by the CMTS due to collisions between at least two modems contending for a first contention slot. The computer readable code further comprises computer code for dynamically adjusting the modem back-off parameters based upon a ratio of the Ns and Nc parameters; and computer code for communicating the dynamically adjusted back-off parameters to the plurality of cable modems. Additionally, the computer program product may include computer code for increasing the back-off start parameter if the ratio of Nc/Ns is greater than a first specified value; and computer code for decreasing the back-off start parameter if the ratio of Nc/Ns is less than a second specified value.